πŸ‘©β€πŸ’» 14502. μ—°κ΅¬μ†Œ

@Seongukbaek Posted March 19, 2022 Β· Updated March 19, 2022 Β· 8 min read

문제

인체에 치λͺ…적인 λ°”μ΄λŸ¬μŠ€λ₯Ό μ—°κ΅¬ν•˜λ˜ μ—°κ΅¬μ†Œμ—μ„œ λ°”μ΄λŸ¬μŠ€κ°€ μœ μΆœλ˜μ—ˆλ‹€. λ‹€ν–‰νžˆ λ°”μ΄λŸ¬μŠ€λŠ” 아직 퍼지지 μ•Šμ•˜κ³ , λ°”μ΄λŸ¬μŠ€μ˜ 확산을 막기 μœ„ν•΄μ„œ μ—°κ΅¬μ†Œμ— 벽을 μ„Έμš°λ €κ³  ν•œλ‹€. μ—°κ΅¬μ†ŒλŠ” 크기가 NΓ—M인 μ§μ‚¬κ°ν˜•μœΌλ‘œ λ‚˜νƒ€λ‚Ό 수 있으며, μ§μ‚¬κ°ν˜•μ€ 1Γ—1 크기의 μ •μ‚¬κ°ν˜•μœΌλ‘œ λ‚˜λˆ„μ–΄μ Έ μžˆλ‹€. μ—°κ΅¬μ†ŒλŠ” 빈 μΉΈ, 벽으둜 이루어져 있으며, 벽은 μΉΈ ν•˜λ‚˜λ₯Ό 가득 μ°¨μ§€ν•œλ‹€. 일뢀 칸은 λ°”μ΄λŸ¬μŠ€κ°€ μ‘΄μž¬ν•˜λ©°, 이 λ°”μ΄λŸ¬μŠ€λŠ” μƒν•˜μ’Œμš°λ‘œ μΈμ ‘ν•œ 빈 칸으둜 λͺ¨λ‘ νΌμ Έλ‚˜κ°ˆ 수 μžˆλ‹€. μƒˆλ‘œ μ„ΈμšΈ 수 μžˆλŠ” 벽의 κ°œμˆ˜λŠ” 3개이며, κΌ­ 3개λ₯Ό μ„Έμ›Œμ•Ό ν•œλ‹€. 예λ₯Ό λ“€μ–΄, μ•„λž˜μ™€ 같이 μ—°κ΅¬μ†Œκ°€ 생긴 경우λ₯Ό μ‚΄νŽ΄λ³΄μž.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

μ΄λ•Œ, 0은 빈 μΉΈ, 1은 λ²½, 2λŠ” λ°”μ΄λŸ¬μŠ€κ°€ μžˆλŠ” 곳이닀. μ•„λ¬΄λŸ° 벽을 μ„Έμš°μ§€ μ•ŠλŠ”λ‹€λ©΄, λ°”μ΄λŸ¬μŠ€λŠ” λͺ¨λ“  빈 칸으둜 νΌμ Έλ‚˜κ°ˆ 수 μžˆλ‹€. 2ν–‰ 1μ—΄, 1ν–‰ 2μ—΄, 4ν–‰ 6열에 벽을 μ„Έμš΄λ‹€λ©΄ μ§€λ„μ˜ λͺ¨μ–‘은 μ•„λž˜μ™€ κ°™μ•„μ§€κ²Œ λœλ‹€.

2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

λ°”μ΄λŸ¬μŠ€κ°€ 퍼진 λ’€μ˜ λͺ¨μŠ΅μ€ μ•„λž˜μ™€ κ°™μ•„μ§„λ‹€.

2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

벽을 3개 μ„Έμš΄ λ’€, λ°”μ΄λŸ¬μŠ€κ°€ 퍼질 수 μ—†λŠ” 곳을 μ•ˆμ „ μ˜μ—­μ΄λΌκ³  ν•œλ‹€. μœ„μ˜ μ§€λ„μ—μ„œ μ•ˆμ „ μ˜μ—­μ˜ ν¬κΈ°λŠ” 27이닀. μ—°κ΅¬μ†Œμ˜ 지도가 μ£Όμ–΄μ‘Œμ„ λ•Œ 얻을 수 μžˆλŠ” μ•ˆμ „ μ˜μ—­ 크기의 μ΅œλŒ“κ°’μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…, 좜λ ₯

μž…λ ₯

  • 첫째 쀄에 μ§€λ„μ˜ μ„Έλ‘œ 크기 Nκ³Ό κ°€λ‘œ 크기 M이 μ£Όμ–΄μ§„λ‹€. (3 ≀ N, M ≀ 8)
  • λ‘˜μ§Έ 쀄뢀터 N개의 쀄에 μ§€λ„μ˜ λͺ¨μ–‘이 μ£Όμ–΄μ§„λ‹€. 0은 빈 μΉΈ, 1은 λ²½, 2λŠ” λ°”μ΄λŸ¬μŠ€κ°€ μžˆλŠ” μœ„μΉ˜μ΄λ‹€. 2의 κ°œμˆ˜λŠ” 2보닀 ν¬κ±°λ‚˜ κ°™κ³ , 10보닀 μž‘κ±°λ‚˜ 같은 μžμ—°μˆ˜μ΄λ‹€.
  • 빈 칸의 κ°œμˆ˜λŠ” 3개 이상이닀.

좜λ ₯

  • 첫째 쀄에 얻을 수 μžˆλŠ” μ•ˆμ „ μ˜μ—­μ˜ μ΅œλŒ€ 크기λ₯Ό 좜λ ₯ν•œλ‹€.

πŸ“ Logic

class Lab { Queue<Loc> locQueue; int N, M; int safeArea = 0; int[][] map; int[][] copyMap; int[] rangeX = { -1, 0, 1, 0 }; int[] rangeY = { 0, 1, 0, -1 }; Loc[] orgSafe; int idx0 = 0; ... }
  • μ—°κ΅¬μ†Œμ˜ 정보λ₯Ό κ΄€λ¦¬ν•˜λŠ” 클래슀
  • 원본 μ—°κ΅¬μ†Œ 정보λ₯Ό μ €μž₯ν•˜λŠ” map κ³Ό λ°”μ΄λŸ¬μŠ€λ₯Ό μ‹€μ œλ‘œ 퍼뜨릴 copyMap 을 μ‚¬μš©ν•œλ‹€.
  • λ˜ν•œ 벽을 μ„ΈμšΈ 곡간듀을 μ €μž₯ν•˜λŠ” orgSafe 배열을 μ‚¬μš©ν•œλ‹€.
  • setWall() μž¬κ·€ 호좜둜 벽을 μ„Έμš°κ³ , 벽을 λ‹€ μ„Έμš΄ λ‹€μŒ, spreadVirus() μ—μ„œ BFS λ°©μ‹μœΌλ‘œ λ°”μ΄λŸ¬μŠ€λ₯Ό νΌλœ¨λ¦°λ‹€.
  • 이후, countAndReset() 으둜 λ°”μ΄λŸ¬μŠ€κ°€ 퍼진 μ΄ν›„μ˜ μ•ˆμ „ μ˜μ—­μ„ μΉ΄μš΄νŠΈν•˜κ³ , map 을 μ΄μš©ν•΄ copyMap 을 λ°”μ΄λŸ¬μŠ€κ°€ 퍼지기 μ „ μƒνƒœλ‘œ λŒλ €λ†“λŠ”λ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; class Loc { int x, y; public Loc(int x, int y) { this.x = x; this.y = y; } } class Lab { Queue<Loc> locQueue; int N, M; int safeArea = 0; int[][] map; int[][] copyMap; int[] rangeX = { -1, 0, 1, 0 }; int[] rangeY = { 0, 1, 0, -1 }; Loc[] orgSafe; int idx0 = 0; public Lab (int N, int M) { this.N = N; this.M = M; map = new int[N][M]; copyMap = new int[N][M]; orgSafe = new Loc[N*M]; locQueue = new LinkedList<>(); } public int findMaxSafeArea() { setWall(0,3); return safeArea; } private void setWall(int idx, int count) { if (count == 0) { spreadVirus(); int result = countAndReset(); if (safeArea < result) safeArea = result; } else { count--; for (int i = idx; i < idx0; i++) { copyMap[orgSafe[i].x][orgSafe[i].y] = 1; setWall(i + 1, count); copyMap[orgSafe[i].x][orgSafe[i].y] = 0; } } } private void spreadVirus() { for (int i = 0; i < locQueue.size(); i++) { Loc tmpLoc = locQueue.poll(); bfs(tmpLoc.x, tmpLoc.y); locQueue.add(tmpLoc); } } private void bfs(int x, int y) { Queue<Loc> queue = new LinkedList<>(); queue.add(new Loc(x, y)); while (!queue.isEmpty()){ Loc tmp = queue.poll(); for (int i = 0; i < 4; i++) { int nx = tmp.x + rangeX[i], ny = tmp.y + rangeY[i]; if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if (copyMap[nx][ny] == 0) { queue.add(new Loc(nx, ny)); copyMap[nx][ny] = 2; } } } } private int countAndReset() { int count = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (copyMap[i][j] == 0) count++; if (copyMap[i][j] == 2) { if (locQueue.contains(new Loc(i, j))) continue; copyMap[i][j] = map[i][j]; } } } return count; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split(" "); int N = Integer.parseInt(line[0]); int M = Integer.parseInt(line[1]); Lab lab = new Lab(N, M); for (int i = 0; i < N; i++) { lab.map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); for (int j = 0; j < M; j++) { if (lab.map[i][j] == 2) lab.locQueue.add(new Loc(i, j)); else if (lab.map[i][j] == 0) lab.orgSafe[lab.idx0++] = new Loc(i, j); lab.copyMap[i][j] = lab.map[i][j]; } } br.close(); System.out.println(lab.findMaxSafeArea()); } }

✏️ Review

  • μ›λž˜μ˜ μ—°κ΅¬μ†Œ 정보λ₯Ό κ°„μ§ν•˜κΈ° μœ„ν•΄ map κ³Ό copyMap 배열을 두고 μ§„ν–‰ν–ˆλŠ”λ°, 계속 두 배열이 λ™κΈ°ν™”λœ κ²ƒλ§ˆλƒ₯ 값이 같이 λ³€κ²½λ˜κ³  μžˆμ—ˆλ‹€. μ•„λ¬΄λž˜λ„ lab.map[i] = lab.copyMap[i]; 이 μ½”λ“œ λ•Œλ¬Έμ— μΈμŠ€ν„΄μŠ€μ˜ μ£Όμ†Œ κ³΅μœ λ‚˜ 참쑰의 문제일거라 생각해 κ²€μƒ‰ν•΄λ³΄λ‹ˆ μ•„λ‹ˆλ‚˜ λ‹€λ₯ΌκΉŒ "얕은 볡사와 κΉŠμ€ 볡사" λ¬Έμ œμ˜€λ‹€. ν•œ 번 정리해야겠닀.
  • λ°”μ΄λŸ¬μŠ€κ°€ 퍼진 이후 λ‹€μ‹œ μ›μƒλ³΅κ΅¬ν• λ•Œ, μ„Έμš΄ λ²½κΉŒμ§€ μ—†μ• λ²„λ¦¬λŠ” μ΄ˆκΈ°ν™” 과정떄문에 값이 계속 잘λͺ» λ‚˜μ™”λ‹€. μ΄ˆκΈ°ν™” 과정은 항상 잘 ν™•μΈν•˜μž.

πŸ“• 좜처

Baekjoon : https://www.acmicpc.net/problem/14502

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€